import os
import random

# ===========================================
# 配置区
inputPath = './input/'
outputPath = './output/'
# 种群长度
length = 10

# 迭代次数
NN = 1000
# ===========================================
# 全局种群
population = []
entites = []
# 工件个数
Gnum = 0
# 机器个数
Mnum = 0

def is_dominated_dict(candidate, other):
    return all(candidate[k] >= other[k] for k in ['process', 'delay']) and \
           any(candidate[k] > other[k] for k in ['process', 'delay'])
def pareto_layering_dict(solutions):
    layers = []
    remaining_solutions = solutions[:]
    while remaining_solutions:
        layer = []
        non_dominated = []

        for candidate in remaining_solutions:
            if not any(is_dominated_dict(candidate, other) for other in remaining_solutions if other is not candidate):
                layer.append(candidate)
            else:
                non_dominated.append(candidate)

        layers.append(layer)
        remaining_solutions = non_dominated

    return layers
def readFile(filename):
    global entites, Gnum, Mnum
    with open(filename, 'r') as file:
        # 工件个数
        Gnum = int(file.readline())
        # 机器个数
        Mnum = int(file.readline())
        file.readline()
        while True:
            flag = 0
            entity = {}
            for i in range(0, 3):
                line = file.readline()
                if not line:
                    flag = 1
                    break
                if i == 0:
                    continue
                if i == 1:
                    entity['delay'] = int(line.strip())
                if i == 2:
                    entity['processing_time'] = list(map(int, line.strip().split()))
            entites.append(entity)
            if flag == 1:
                break

def calculate_total_time(schedule):
    total_time = 0
    total_delay_time = 0
    delay_time = []
    for item in schedule:
        times = entites[item]['processing_time']
        curryTime = 0
        # 对于第一个工件直接相加
        if item == schedule[0]:
            for i in times:
                curryTime += i
                delay_time.append(curryTime)
        # 其他工件需要计算延迟时间
        else:
            for index, i in enumerate(times):
                # 第一个机器都会有延迟，直接加上延迟表中的第一项
                if index == 0:
                    # 更新当前时间
                    curryTime += delay_time[0] + i
                    # 更新延迟时间
                    delay_time[0] = curryTime
                else:
                    # 需要判断当前时间是否大于等于前一个工件的加工时间
                    if delay_time[index - 1] >= delay_time[index]:
                        curryTime += i
                        delay_time[index] = curryTime
                    # 否则需要加上上一个的等待时间
                    else:
                        # 时间差值
                        de = delay_time[index] - delay_time[index - 1]
                        curryTime = curryTime + de + i
                        delay_time[index] = curryTime
        # 计算延迟时间
        if delay_time[Mnum - 1] > entites[item]['delay']:
            total_delay_time += (delay_time[Mnum - 1] - entites[item]['delay'])
        # 计算总加工时间
        total_time += delay_time[Mnum - 1]
    # print(total_time)
    return total_time, total_delay_time


# 计算两个解和其他解的加工时间和延迟时间的差
def I(x1, x2):
    return max((x1['process'] - x2['process']), (x1['delay'] - x2['delay']))


# 初始化种群
def init():
    global population
    population = []
    random_numbers = list(range(Gnum))
    for i in range(0, length):
        random.shuffle(random_numbers)
        result_array = random_numbers[:Gnum]
        item = {}
        item['array'] = result_array
        item_time = calculate_total_time(result_array)
        # 计算总加工时间
        item['process'] = int(item_time[0])
        # 计算总延迟时间
        item['delay'] = (item_time[1])
        # 计算适应值
        item['fit'] = 0
        # flag
        item['flag'] = 0
        population.append(item)
    fitness()


# 计算种群的适应值
def fitness():
    for i, item in enumerate(population):
        fit = 0
        for j, item2 in enumerate(population):
            if i != j:
                fit += I(population[i], population[j])
        population[i]['fit'] = fit
        # print('fit = ',fit)

def addfit(it):
    # 更新原种群的fit
    fit_i = 0
    for i, item in enumerate(population):
        fit = I(item,it)
        population[i]['fit'] += fit
        # 计算当前it的fit
        fit_i += I(it,item)
    it['fit'] = fit_i
    return it


# 更新标志位
def flagUpdate():
    n = len(population)
    for i in range(0, n):
        for j in range(0, n):
            if i != j:
                # 有解 在两个目标上严格占优自己
                if population[i]['process'] > population[j]['process'] and \
                        population[i]['delay'] > population[j]['delay']:
                    # 更新标志位
                    population[i]['flag'] = 1
                    break

# 根据当前解生成一个新的解
def getNew(x):
    seek1 = random.randint(0,Gnum-1)
    seek2 = random.randint(0,Gnum-1)
    while seek1 == seek2:
        seek1 = random.randint(0, Gnum-1)
        seek2 = random.randint(0, Gnum-1)
    # 交换
    temp = x['array'][seek1]
    x['array'][seek1] = x['array'][seek2]
    x['array'][seek2] = temp

    item_time = calculate_total_time(x['array'])
    # 计算总加工时间
    x['process'] = int(item_time[0])
    # 计算总延迟时间
    x['delay'] = (item_time[1])

    x['fit'] = 0
    x['flag'] = 0

    population.append(x)
# 判断当前解的array是否已经存在
def isExist(x):
    for i in population:
        if x == i['array']:
            return True
    return False

def getNew1(x):
    # print(x)
    seek1 = random.randint(0,Gnum-1)
    seek2 = random.randint(0,Gnum-1)
    while seek1 == seek2:
        seek1 = random.randint(0, Gnum-1)
        seek2 = random.randint(0, Gnum-1)
    # 交换
    temp = x['array'][seek1]
    x['array'][seek1] = x['array'][seek2]
    x['array'][seek2] = temp

    item_time = calculate_total_time(x['array'])
    # 计算总加工时间
    x['process'] = int(item_time[0])
    # 计算总延迟时间
    x['delay'] = (item_time[1])
    x['fit'] = 0
    x['flag'] = 0
    return x
def deleteFit(index):
    it = population.pop(index)
    for i, item in enumerate(population):
        fit = I(item,it)
        population[i]['fit'] -= fit


# main单次计算的入口函数
def main(filename):
    print(filename)
    global population,length
    # 1. 读取数据
    readFile(inputPath + filename + '.txt')
    # 2. 初始化种群
    init()

    layes = pareto_layering_dict(population)
    population = layes[0]
    length = len(population)
    # print("===========",)
    # for inite in layes[0]:
    #     print(inite['process'],inite['delay'])
    # for i in population:
    #     print(i)
    # 3. 刷新标志位
    # flagUpdate()
    # 4. 迭代
    i = 0
    while True:
        if i >= NN:
            break
        i += 1
        # 开始迭代
        # 生成一个新的解，按照种群的顺序
        newitem = getNew1(population[i%length])
        population.append(newitem)

        layes = pareto_layering_dict(population)
        population = layes[0]
        length = len(population)

    #
    #     fitness()
    #     print(population)
    #     # print(population)
    #     # 对适应值进行排序
    #     population = sorted(population, key=lambda x: x['fit'])
    #     # for item in population:
    #     #     print(item['array'],'_',item['fit'])
    #     pop_i = population.pop()
    #     newitem = getNew1(pop_i)
    #
    #     flagUpdate()
    #     findex = 0
    #     # 删除标志位为0
    #     for index,item in enumerate(population):
    #         if item['flag'] == 0:
    #             # 删除此元素
    #             population.pop(index)
    #             # 新增
    #             population.append(getNew1(item))
    #             # findex+=1
    #
    #     population.append(newitem)
    #
    # 输入到文件
    with open(outputPath + filename + '.txt', 'w') as file:
        for i in population:
            line = 'process = {}, delay = {}, fit = {}, flag = {}'.format(i['process'], i['delay'], i['fit'], i['flag'])
            file.write(line + '\n')


if __name__ == "__main__":
    for root, dirs, files in os.walk(inputPath):
        for file in files:
            # 初始化全局变量
            Mnum = 0
            Gnum = 0
            population = []
            entites = []
            file_name = file[:-4]
            main(file_name)

